package leetcode.editor.cn;
 
/**
 * 打家劫舍 II
 * @author qulq
 * @date 2024-07-28 08:38:34
 */
public class T213_HouseRobberIi{
	 public static void main(String[] args) {
	 	 // 测试代码
		 Solution solution = new T213_HouseRobberIi().new Solution();
		 System.out.println(solution.rob(new int[]{1}));
	 }

	/**
	 * 同打家劫舍1，两种情况
	 * 1、不偷An的情况下，最大偷多少 2、不偷A1的情况下，最大偷多少
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
		if (nums.length <= 1) {
			return nums[0];
		}
		int ans;
		int[] dp = new int[nums.length + 1];
		// 不偷An, 可以偷A1, 求前n-1个房子
		dp[0] = 0;
		dp[1] = nums[0];
		for (int i = 2; i <= nums.length - 1; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		ans = dp[nums.length - 1];
		// 不偷A1, 可以偷An
		dp[0] = 0;
		dp[1] = 0;
		for (int i = 2; i <= nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		return Math.max(ans, dp[nums.length]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}